package sort;

/**
 * 堆排序
 */
public class HeapSort {
    public static void main(String[] args) {
        //给定一个数组,将其变成堆的方式存储
        int[] heap ={1,2,4,3,5,7,6,9,8,10};
        int usedSize = heap.length;
        heapSort(heap,usedSize);
        for (int x: heap) {
            System.out.print(x + " ");
        }
    }
    //建立大根堆
    public static void heapSort(int[] heap,int usedSize){
        //堆排序从最后一个父节点开始调整
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize,heap);
        }
    }
    //向下调整,结束位置不能超过数组长度
    public static void shiftDown(int parent,int len,int[] heap){
        // 找到传入父节点孩子节点的下标
        int child = parent * 2 + 1;
        // 判断孩子节点是否存在
        while (child < len){
            //判断左右孩子节点的值谁更大
            if(child + 1 < len && heap[child] < heap[child + 1]){
                 child ++;
            }
            //child下标 一定是左右孩子最大值的下标
            if(heap[child] > heap[parent]){
                swap(child,parent,heap);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
    public static void swap(int start,int end,int[] heap){
        int tmp = heap[start];
        heap[start] = heap[end];
        heap[end] = tmp;
    }
}
